/*
这次的要求不是把方法打印出来，而是把整个棋盘打印出来
*/  
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
	vector<vector<string>> result;
	bool check(int row,int col,vector<string>& chessboard,int n){
		for(int i=0;i<row;i++){
			if(chessboard[i][col]=='Q'){
				return false;
			}
		}
		//左上斜线 
		for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
			if(chessboard[i][j]=='Q'){
				return false;
			}
		}
		//右上斜线
		for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
			if(chessboard[i][j]=='Q'){
				return false;
			}
		} 
		return true;
	}
	
	//n就是棋盘的大小，row是当前递归到第几行了 
	void backtracking(int n,int row,vector<string>& chessboard){
		if(row==n){
			result.push_back(chessboard);
			return ;
		} 
		for(int col=0;col<n;col++){
			if(check(row,col,chessboard,n)){
				chessboard[row][col]='Q';
				backtracking(n,row+1,chessboard);
				chessboard[row][col]='.';
			}
		}
	}
	
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n,string(n,'.'));
        backtracking(n,0,chessboard);
        return result;
    }
};